package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC636 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 雕虫小技，何足道哉！
     * @return:
     */
    public class Solution {
        public int[] exclusiveTime(int n, List<String> logs) {
            Stack<Integer> stack = new Stack<>();
            int[] res = new int[n];
            String[] s = logs.get(0).split(":");
            stack.push(Integer.parseInt(s[0]));
            int i = 1, prev = Integer.parseInt(s[2]);
            while (i < logs.size()) {
                s = logs.get(i).split(":");
                if (s[1].equals("start")) {
                    if (!stack.isEmpty())
                        res[stack.peek()] += Integer.parseInt(s[2]) - prev;
                    stack.push(Integer.parseInt(s[0]));
                    prev = Integer.parseInt(s[2]);
                } else {
                    res[stack.peek()] += Integer.parseInt(s[2]) - prev + 1;
                    stack.pop();
                    prev = Integer.parseInt(s[2]) + 1;
                }
                i++;
            }
            return res;
        }
    }


    class Solution_Wrong_Idea {
        public int[] exclusiveTime(int n, List<String> logs) {
            TreeSet<int[]>[] idCount = new TreeSet[n];
            for (String log : logs) {
                final String[] logLine = log.split(":");
                String action = logLine[1];
                int id = Integer.parseInt(logLine[0]), timeStamp = Integer.parseInt(logLine[2]);

                if (idCount[id] == null) {
                    TreeSet<int[]> treeSet = new TreeSet<>(new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            return o1[0] - o2[0];
                        }
                    });

                    idCount[id] = treeSet;
                }

                if ("start".equals(action)) {
                    idCount[id].add(new int[]{timeStamp, Integer.MAX_VALUE});
                    continue;
                } else {
                    // current is an end, we need to find it corresponding start timeStamp.
                    int[] nearestInterval = idCount[id].floor(new int[]{timeStamp, Integer.MAX_VALUE});
                    // if (null == nearestInterval) not possible to happen.
                    nearestInterval[1] = timeStamp;
                }
            }

            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                for (int[] interval : idCount[i]) {
                    res[i] += interval[1] - interval[0] + 1;
                }
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<String> logs = Arrays.asList(InputUtil.toStringArray("[\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]"));
        System.out.println(solution.exclusiveTime(2, logs));
    }

    public static void main(String[] args) throws Exception {
        LC636 an = new LC636();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
